#include<iostream>
#include<stdio.h>
using namespace std;
void CreateMatrix(int N,int **&A)//为数组行指针分配内存
{
    A=new int *[N];
}
void MallocMatrix(int N,int **A)//为矩阵元素分配内存
{
    for(int i=0;i<N;i++)
    {
        A[i]=new int[N];
    }
}
void FreeMatrix(int N,int **A)//释放矩阵元素内存
{
    for(int i=0;i<N;i++)
    {
        delete [] A[i];
    }
   // delete [] A;
}
void MatrixApart(int N,int **A,int **&A11,int **&A12,int **&A21,int **&A22)
//矩阵分块
{
    for(int i=0;i<N/2;i++)
    {
        A11[i]=A[i];
    }
    for(int i=0;i<N/2;i++)
    {
        A12[i]=A[i]+N/2;
    }
    for(int i=0;i<N/2;i++)
    {
        A21[i]=A[i+N/2];
    }
    for(int i=0;i<N/2;i++)
    {
        A22[i]=A[i+N/2]+N/2;
    }
}
void MatrixAddition(int N,int **A,int **B,int **C)
//矩阵加法
{
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            C[i][j]=A[i][j]+B[i][j];
        }
    }

}
void MatrixSubtract(int N,int **A,int **B,int **C)
//矩阵减法
{
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            C[i][j]=A[i][j]-B[i][j];
        }
    }

}
void Strassen(int N,int **A,int **B,int **C)//N=2^k
{
   
    if(N==1)
    {
        C[0][0]=A[0][0]*B[0][0];
        return ;
    }
    int **A11,**A12,**A22,**A21,**B11,**B12,**B21,**B22;
    int **C11,**C12,**C21,**C22;
    CreateMatrix(N/2,A11);
    CreateMatrix(N/2,A12);
    CreateMatrix(N/2,A21);
    CreateMatrix(N/2,A22);
    CreateMatrix(N/2,B11);
    CreateMatrix(N/2,B12);
    CreateMatrix(N/2,B21);
    CreateMatrix(N/2,B22);
    CreateMatrix(N/2,C11);
    CreateMatrix(N/2,C12);
    CreateMatrix(N/2,C21);
    CreateMatrix(N/2,C22);
    int **S[10];
    int **P[7];
    for(int i=0;i<10;i++)
    {
        CreateMatrix(N/2,S[i]);
        MallocMatrix(N/2,S[i]);
    }
    for(int i=0;i<7;i++)
    {
        CreateMatrix(N,P[i]);
        MallocMatrix(N,P[i]);
    }
    MatrixApart(N,A,A11,A12,A21,A22);
    MatrixApart(N,B,B11,B12,B21,B22);
    MatrixApart(N,C,C11,C12,C21,C22);
    MatrixSubtract(N/2,B12,B22,S[0]);
    MatrixAddition(N/2,A11,A12,S[1]);
    MatrixAddition(N/2,A21,A22,S[2]);
    MatrixSubtract(N/2,B21,B11,S[3]);
    MatrixAddition(N/2,A11,A22,S[4]);
    MatrixAddition(N/2,B11,B22,S[5]);
    MatrixSubtract(N/2,A12,A22,S[6]);
    MatrixAddition(N/2,B21,B22,S[7]);
    MatrixSubtract(N/2,A11,A21,S[8]);
    MatrixAddition(N/2,B11,B12,S[9]);

    //7次乘法
    Strassen(N/2,A11,S[0],P[0]);
    Strassen(N/2,S[1],B22,P[1]);
    Strassen(N/2,S[2],B11,P[2]);
    Strassen(N/2,A22,S[3],P[3]);
    Strassen(N/2,S[4],S[5],P[4]);
    Strassen(N/2,S[6],S[7],P[5]);
    Strassen(N/2,S[8],S[9],P[6]);
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            C[i][j]=0;
        }
    }
    MatrixAddition(N/2,P[4],P[3],C11);
    MatrixSubtract(N/2,C11,P[1],C11);
    MatrixAddition(N/2,C11,P[5],C11);
    //C11=P4+P3-P1+P5
    MatrixAddition(N/2,P[0],P[1],C12);
    //C12=P0+P1
    MatrixAddition(N/2,P[2],P[3],C21);
    //C21=P2+P3
    MatrixAddition(N/2,P[4],P[0],C22);
    MatrixSubtract(N/2,C22,P[2],C22);
    MatrixSubtract(N/2,C22,P[6],C22);
    //C22=P4+P0-P2-P6
    for(int i=0;i<10;i++)
    {
        FreeMatrix(N/2,S[i]);
    }
    for(int i=0;i<7;i++)
    {
        FreeMatrix(N/2,P[i]);
    }
    delete [] A11;
    delete [] A12;
    delete [] A21;
    delete [] A22;
    delete [] B11;
    delete [] B12;
    delete [] B21;
    delete [] B22;
    delete [] C11;
    delete [] C12;
    delete [] C21;
    delete [] C22;


}
int main()
{
    int N;
    cout<<"Pleased enter dimension N (=2^k)of matrix : ";
    cin>>N;
    int **A,**B,**C;
    CreateMatrix(N,A);
    CreateMatrix(N,B);
    CreateMatrix(N,C);
    MallocMatrix(N,A);
    MallocMatrix(N,B);
    MallocMatrix(N,C);


    cout<<"Please enter matrix A:\n";
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)

        {
           cin>> A[i][j];
        }
    }
    cout<<"Please enter matrix B:\n";
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
           cin>> B[i][j];
        }
    }
    
    Strassen(N,A,B,C);
    cout<<"A*B=\n";
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
           printf( "%4d",C[i][j]);
        }
        cout<<endl;
    }
    FreeMatrix(N,A);
    FreeMatrix(N,B);
    FreeMatrix(N,C);
    delete [] A;
    delete [] B;
    delete [] C;
    return 0;
    
}

